package done.normal_001_100;

import com.study.common.TreeNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;
import static com.study.util.SwapUtil.swap;

/**
 * 99. Recover Binary Search Tree 恢复二叉搜索树
 * <p>
 * 二叉搜索树中的两个节点被错误地交换。
 * 请在不改变其结构的情况下，恢复这棵树。
 * <p>
 * 示例 1: 输入: [3,1,4,null,null,2]
 * <p>
 * 3
 * / \
 * 1   4
 * /
 * 2
 * <p>
 * 输出: [2,1,4,null,null,3]
 * <p>
 * 2
 * / \
 * 1   4
 * /
 * 3
 * <p>
 * 中序遍历过程中，记录错误两个错误排序节点，最后进行交换
 * 只需要中序遍历一遍就可以了
 * <p>
 * 首先我们来看中序遍历过程模板
 * <p>
 * 另一方面我们知道 对二叉搜索树进行 中序遍历的时候 访问到的元素是从小到大顺序排列的
 * 如我们对实例 2 恢复好的树 进行中序遍历 得到的应该是  1 2 3 4
 * <p>
 * 那这道题我们就有了大致思路
 * 我们对错误的二叉树进行 中序遍历 那我们按顺序访问到的数应该是按顺序排列的
 * 那如果对两个节点交换了顺序  那一定有两个地方是  不满足  前一个元素 < 当前元素 < 后一个元素
 * 如示例2      3  1  4   2：
 * 3  这个节点不满足      1 这个节点不满足
 * 所以我们使用两个全局变量在遍历过程中记录这两个节点 最后对他们进行交换
 * <p>
 * 2019-05-07 22:21
 **/
@SuppressWarnings("all")
public class RecoverBinarySearchTree {

    public void recoverTree(TreeNode root) {
        // 190509 first
        // 190511 second 做出来了
        // 190602 third 忘了看答案做出来了
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                1, new TreeNode(4,
                2));
        recoverTree(root);
        info(root);
    }
}













































/*
TreeNode t1;
TreeNode t2;
TreeNode pre;

public void recoverTree(TreeNode root) {
    inorder(root);
    swap(t1, t2);
}

public void inorder(TreeNode root){
    if (root == null)
        return;

    inorder(root.left);

    if (pre != null && pre.val > root.val) {
        if (t1 == null)
            t1 = pre;
        t2 = root;
    }

    pre = root;

    inorder(root.right);
}
*/
